The present invention relates to digital signal processing, and more particularly to digital signal decompression.
The advancement of fast computers in recent years has caused a large capacity of data to be treated in the computer. Typically, the data are compressed to efficiently use available memory and reduce data transmission times. A variety of data compression methods are known. One compression method, known as Huffman coding, is a form of statistical coding wherein a probability of each data character is translated to a sequence of bits.
Traditional Huffman coding assigns an optimal prefix-free code for each symbol based on a frequency with which each symbol appears in the file. Symbols that appear more frequently are coded in fewer bits. In standard Huffman coding this is accomplished by building a binary tree structure. This tree structure is then used to build the codewords. Decoding the codeword requires that the tree is traversed until the root is reached. Traversing the tree structure requires that the binary tree be stored in the file, and requires numerous accesses to memory as the tree is traversed.
FIG. 1 illustrates one example of the xe2x80x9ccode treexe2x80x9d generated by the Huffman encoding. Nodes are points marked with a circle O and a square. A line segment connecting the nodes is called a xe2x80x9cbranch.xe2x80x9d The node located in the highest position is called a xe2x80x9croot.xe2x80x9d Further, an under node Y connected via the xe2x80x9cbranchxe2x80x9d to a node X is termed a xe2x80x9cchildxe2x80x9d of the node X. Reversely, the node X is referred to as a xe2x80x9cparentxe2x80x9d of the node Y. A node having no xe2x80x9cchildxe2x80x9d is called a xe2x80x9cleaf,xe2x80x9d and a particular character corresponds to each xe2x80x9cleaf.xe2x80x9d Further, the nodes excluding the xe2x80x9cleavesxe2x80x9d are referred to as xe2x80x9cinternal nodes,xe2x80x9d and the number of xe2x80x9cbranchesxe2x80x9d from the xe2x80x9crootxe2x80x9d down to each xe2x80x9cnodexe2x80x9d is called a level.
When encoded by use of the code tree, a path extending from the xe2x80x9crootxe2x80x9d down to a target xe2x80x9cleafxe2x80x9d (corresponding to a character to be encoded) is outputted as a code. More specifically, xe2x80x9c1xe2x80x9d is outputted when branching off to the left from each of the nodes from the xe2x80x9crootxe2x80x9d down to a target xe2x80x9cleaf,xe2x80x9d while xe2x80x9c0xe2x80x9d is outputted when branching off to the right. For example, in the code tree illustrated in FIG. 1, a code xe2x80x9c00xe2x80x9d is outputted for a character A corresponding to a xe2x80x9cleafxe2x80x9d of a node number 7, and a code xe2x80x9c011xe2x80x9d is outputted for a character B corresponding to a xe2x80x9cleafxe2x80x9d of a node number 8.
When decoded, a character is outputted which corresponds to a xe2x80x9cleafxe2x80x9d which is reached by tracing the respective nodes from the xe2x80x9crootxe2x80x9d in accordance with a value of each bit of code defined as a target for decoding.
In general terms, a Huffman encoding algorithm generates the above-described code tree according to the following:
(1) Leaf nodes corresponding to the individual characters are prepared, and the frequency of occurrence of the characters corresponding to the respective leaves are recorded.
(2) One new node is created for two nodes having the minimum occurrence frequency, and this created node is connected via branches to the two nodes. Further, a sum of the occurrence frequencies of the two nodes connected via the branches is recorded as an occurrence frequency of the newly created node.
(3) The processing set forth in item (2) is executed for the remaining nodes, i.e. the nodes not having parents, until the number of remaining nodes becomes 1.
In the code tree thus generated, a code is allocated to each character with a code length which is inversely proportional to the occurrence frequency of the character. Therefore, when the coding is performed by use of the code tree, it follows that the data can be compressed.
This data must be decompressed before it is used.
The Huffman encoding algorithm was introduced in the early 1950""s. In subsequent years it has been characterized, analyzed and expanded to include canonical forms. A canonical Huffman code is an optimal prefix-free code, but the code is not generated using the standard Huffman coding. Instead, Huffman""s algorithm is used to calculate the length in bits of each codeword, but a different algorithm is used to determine the actual codewords. The codewords are chosen such that a small look-up table is all that is needed to determine when a codeword has been assembled, then the decoded symbol can be accessed directly from another small look-up table containing the decoded symbols.
As shown in FIG. 2, a canonical Huffman encode file consists of three tables: FIRSTCODE table 1, SYMBOL POINTER table 2, and SYMBOL table 3; and the compressed data. The FIRSTCODE table 1 has one entry assigned to it for each codeword of a given length. For example if the largest codeword length is 10 bits then the FIRSTCODE table 1 would have 10 table entries. The FIRSTCODE table 1 is organized with the code for length 1 first, down to the code for length N. The values in this table are used to determine when a codeword has been built for decoding. Since the codewords are of varying lengths and no delimiter is used, the codeword bit patterns and the FIRSTCODE table 1 allow for determining when the end of a codeword has been reached. The value in the FIRSTCODE table 1 is equal to the minimum integer value of codewords of that bit length. That is, when assembling the bits when the integer value of the assembled bits is greater than or equal to the value in FIRSTCODE, then a valid codeword is available to decode.
The second table, SYMBOL POINTER table 2, contains a pointer to the first decoded symbol for each bit length. The SYMBOL POINTER table 2 contains one word for each bit length.
The SYMBOL table 3 contains the actual decoded symbol value. The length of the SYMBOL table 3 is equal to the number of symbols to decode. The SYMBOL table 3 is a look-up table of the resolved symbols indexed by address.
Each of these three tables is stored in memory. The compressed data are read and the decompression algorithm is used to extract the original data.
FIG. 2 refers to traditional canonical decoding algorithms wherein a LENGTH COUNTER 4 and working value V are reset to 0. A next bit of compressed data is added to V using an addition function 5. Using a comparison function 6, the result of the add function 5 is compared to a FIRSTCODE value selected by the LENGTH COUNTER 4. If the comparison (V greater than =FIRSTCODE(L)) is FALSE, then the LENGTH COUNTER 4 is incremented; the working value is multiplied by 2 using a left shift operation 7; and the next compressed bit from the compressed data 8 is added to the shifted value. Using the comparison function 6, the resultant is again compared with FIRSTCODE(L). This process is repeated until the comparison (V greater than =FIRSTCODE(L)) is TRUE.
When the comparison is TRUE, a value from the SYMBOL POINTER table 2 is selected by the LENGTH COUNTER and added to the working value V using an addition function 9. The FIRSTCODE value selected by the LENGTH COUNTER 4 is subtracted using a subtraction function 10, and the resultant value is the address for the SYMBOL Table 3, whereby the SYMBOL is resolved. The algorithm is thus essentially a bit comparison process that can take up to N iterations to resolve the SYMBOL.
The decompression, or xe2x80x9cdecoding,xe2x80x9d procedure may be described by the C-language pseudo code in Table 1 below. In the pseudo code, the function performs a traditional canonical Huffman decode algorithm as described above and returns the resolved SYMBOL.
Although effective, this software decompression is time consuming and prevents the software from performing other tasks during decompression.
The present invention provides a fast means for decompression of compressed canonical Huffman encoded data by providing a fast peripheral to decompress the data, thereby off-loading the main processor to do other work in contrast to the prior art devices and methods. The present invention also provides for multiple dedicated decompression peripherals to further increase decompression performance in applications having multiple data requesters.
The decompression algorithm of the present invention is implemented in hardware to provide parallel processing of decompression operations that is much faster than traditional software solutions because multiple parallel paths and functional blocks are utilized to rapidly accomplish the decompression.
According to one aspect of the invention, the decompression algorithm of the invention is embodied as a decompression device for decompression of compressed canonical Huffman encoded data, wherein a relationship is fixed between FIRSTCODE and the compressed data bits according to FIRSTCODE[0] and bit 0, FIRSTCODE [1]and bits 0, 1, FIRSTCODE[2] and bits 0, 1, 2, through FIRSTCODE[N] and bits 0, 1, 2, . . . N; and a relationship is fixed between FIRSTCODE and SYMBOL POINTER according to FIRSTCODE[0] and SYMBOL POINTER[0], FIRSTCODE[1] and SYMBOL POINTER[1], through FIRSTCODE[N] and SYMBOL POINTER[N]. The device of the invention thus includes: a plurality of FIRSTCODE registers each having a FIRSTCODE value associated therewith; a plurality of SYMBOL POINTER registers each having a SYMBOL POINTER value associated therewith; a plurality of comparators each coupled to a different FIRSTCODE register to accept a FIRSTCODE value therefrom and coupled to accept a string of compressed data bits from a memory device having compressed canonical Huffman encoded data stored therein, the comparators being structured to simultaneously compare the FIRSTCODE values with corresponding bits of the string of compressed data bits; a multiplexer coupled to accept a result of each of the comparators, the multiplexer being structured to sequentially examine the results and to select a successful comparison result; a plurality of addition blocks each coupled to a different one of the SYMBOL POINTER registers, one of the addition blocks being associated with a SYMBOL POINTER register corresponding to one of the FIRSTCODE registers having the successful comparison result and being structured to add the value from the corresponding SYMBOL POINTER register to the string of compressed NEXTINPUTWORD data bits; a plurality of subtraction blocks each coupled to a different one of the FIRSTCODE registers and to one of the addition blocks corresponding to one of the FIRSTCODE registers, one of the subtraction blocks being associated with the one of the FIRSTCODE registers having the successful comparison result and being structured to subtract the value of the successful FIRSTCODE register from the result of the corresponding addition block and to output an input address to the multiplexer; and a SYMBOL table coupled to the multiplexer to receive the input address and being structured to responsively output a corresponding resolved symbol.
The order of the addition and subtraction is not critical to the invention. Therefore, while the addition function may precede the subtraction function, the addition and subtraction functions are non-ordered according to the invention. Rather, the FIRSTCODE register may be subtracted from the SYMBOL POINTER register before the compressed data is added to the result.
According to another aspect of the invention, the invention provides a method for decompression of canonical Huffman encoded data.
According to still another aspect of the invention, a processor is coupled to the memory device and operates a logic device. The decompression device is further coupled to the memory for respectively receiving the canonical Huffman encoded data file and outputting the resolved symbols.